package code.oldCode.feishuSpecializedTraining.dynamic;

/**
 * @author 26029
 * @date 2025/3/23
 * @description
 */
public class MyDP4 {
    // 518. 零钱兑换 II
    public int change(int amount, int[] coins) {
        // 这道题是完全背包问题：即可以重复选择，当前行可以用自身来累计dp[i][j - coins[i]]
        // 与之相对的是01背包问题：不能重复选择，当前行只能通过上一行累计dp[i - 1][j - coins[i]]
        // 背包：可重复选，求满足金额的组合数
        int len = coins.length;
        // dp[i][j]表示前i个物品可以组成amount的组合数
        int[][] dp = new int[len][amount + 1];

        // 初始化：只用coins[0]来构成金额
        dp[0][0] = 1;  // 金额为0时只有1种方案
        for (int j = coins[0]; j <= amount; j++) {
            dp[0][j] = dp[0][j - coins[0]];  // 可重复使用coins[0]
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= amount; j++) {
                dp[i][j] = dp[i - 1][j];
                // 这里注意，由于背包物品可以重复选，故dp[i][j]+=的是dp[i][j-coins[i]]而不是dp[i-1][j-coins[i]]
                if (coins[i] <= j) {
                    dp[i][j] += dp[i][j - coins[i]];
                }
            }
        }

        return dp[len - 1][amount];
    }

    // 377. 组合总和 Ⅳ
    public int combinationSum4(int[] nums, int target) {
        // 完全背包问题（可重复选），求和为target的元素组合的个数（顺序相关），本质上是爬楼梯
        // 排列问题要按照背包问题来做的话，不好理解，按爬楼梯来做，爬到target层，每次可以爬num层，从num中选
        // dp[i]表示爬到i的方式数量
        int[] dp = new int[target + 1];
        dp[0] = 1;
        // 如果按照二维dp的背包问题理解，要先循环背包大小，后循环背包物品，不好理解。
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (num <= i)
                    dp[i] += dp[i - num];
            }
        }
        return dp[target];
    }

    // 322. 零钱兑换
    public int coinChange(int[] coins, int amount) {
        // 可以重复选、求装满背包的最小物品数量
        // 转化为爬楼梯，求爬到顶的最少步数！外遍历容量，内遍历物品。
        // dp[i]表示金额为i时的最少硬币数量
        int[] dp = new int[amount + 1];
        // 初始化: 金额为0时，最少硬币数为0
        dp[0] = 0;
        // 外层遍历容量
        for (int i = 1; i <= amount; i++) {
            // 内层遍历物品
            dp[i] = amount + 1;
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        // 如果dp[amount]仍为不可能值，返回-1
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public int coinChange_bp(int[] coins, int amount) {
        // 以背包的角度看
        int len = coins.length;
        int[][] dp = new int[len + 1][amount + 1];
        for (int i = 0; i <= len; i++) {
            dp[i][0] = 0; // 凑成0元需要0个硬币
        }
        for (int i = 1; i <= amount; i++) {
            dp[0][i] = amount + 1; // // 用0种硬币不可能凑成金额j
        }
        // 先遍历物品再遍历容量
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j <= amount; j++) {
                dp[i][j] = dp[i - 1][j]; // 不选i
                if (coins[i - 1] <= j)
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
            }
        }
        return dp[len][amount] > amount ? -1 : dp[len][amount];
    }

    public static void main(String[] args) {
        MyDP4 m = new MyDP4();
        System.out.println(m.coinChange(new int[]{2}, 3));
    }
}
